The approaches described in this section could be pursued, but are not necessarily approaches that have been previously conceived or pursued. Therefore, unless otherwise indicated herein, the approaches described in this section are not prior art to the claims in this application and are not admitted to be prior art by inclusion in this section.
In computer networks such as the Internet, packets of data are sent from a source to a destination via a network of elements including links (communication paths such as telephone or optical lines) and nodes (usually routers directing the packet along one or more of a plurality of links connected to it) according to one of various routing protocols.
One class of routing protocol is the link state protocol. The link state protocol relies on a routing algorithm resident at each node. Each node on the network advertises, throughout the network, links to neighboring nodes and provides a cost associated with each link, which can be based on any appropriate metric such as link bandwidth or delay and is typically expressed as an integer value. A link may have an asymmetric cost, that is, the cost in the direction AB along a link may be different from the cost in a direction BA. Based on the advertised information in the form of a link state packet (LSP) each node constructs a link state database (LSDB), which is a map of the entire network topology and from that constructs generally a single optimum route to each available node based on an appropriate algorithm such as, for example, a shortest path first (SPF) algorithm. As a result a “spanning tree” (SPT) is constructed, rooted at the node and showing an optimum path including intermediate nodes to each available destination node. The results of the SPF are stored in a routing information base (RIB) and based on these results the forwarding information base (FIB) or forwarding table is updated to control forwarding of packets appropriately. When there is a network change an LSP representing the change is flooded through the network by each node adjacent the change, each node receiving the LSP sending it to each adjacent node.
As a result, when a data packet for a destination node arrives at a node (the “first node”), the first node identifies the optimum route to that destination and forwards the packet to the next node along that route. The next node repeats this step and so forth.
It will be noted that in normal forwarding each node decides, irrespective of the node from which it received a packet, the next node to which the packet should be forwarded. In some instances this can give rise to a “loop”. In particular this can occur when the databases (and corresponding forwarding information) are temporarily de-synchronized during a routing transition, that is, where because of a change in the network, a new LSP is propagated. As an example, if node A sends a packet to node Z via node B, comprising the optimum route according to its SPF, a situation can arise where node B, according to its SPF determines that the best route to node Z is via node A and sends the packet back. This can continue for as long as the loop remains although usually the packet will have a maximum hop count after which it will be discarded. Such a loop can be a direct loop between two nodes or an indirect loop around a circuit of nodes.
Problems arise in known systems when multiple changes are advertised successively. A node receiving the corresponding LSPs recalculates the SPF each time. Multiple successive SPF calculations comprise a significant processing burden on the computing node, however.
One known solution is to make use of an “exponential back off algorithm” to compute successively increasing delays between receipt of LSPs and subsequent calculation of the SPF if multiple LSPs are received in quick succession. An exponential back-off approach for use in transport protocols is described, for example, in P. Karn et al., “Improving Round-trip Time Estimates in Reliable Transport Protocols,” ACM SIGCOMM Computer Communication Review, at 67, and can be adapted for use in SPF calculation. One such algorithm is explained here with reference to FIG. 1 which is a high-level flow diagram illustrating operation of such an algorithm. The algorithm operation is based on three parameters termed here A, B and C and which are defined as follows:
A is the maximum permitted delay between two consecutive SPF computations;
B is the initial delay interval that is applied when the router or computing node has to run an SPF for the first time or after a “quiet period” (which is discussed in more detail below); and
C is the “secondary wait” or increment that is added to the delay interval in the manner described below.
The “quiet period” can be any predetermined period of time during which no SPF computations have been triggered in which case the initial delay B can be set as the delay period. Here the “quiet period” is set at a period 2*A.
Referring to the flow diagram of FIG. 1, in block 102 the computing node receives the LSP. In block 104 the node checks whether there has been a quiet period, that is, whether the node has run any SPF during the preceding period 2*A. If there has been a quiet period then at block 106 the node sets the routing calculation delay as the initial delay B. In block 108 the node sets a value next_delay=C and then loops back to block 102.
If, in block 104, the node detects that there has not been a quiet period, that is, there has been a SPF calculation within the preceding period 2*A, then at block 110 the node sets the delay value to next_delay−elapsed_time_since_last_SPF. In block 112 the node increments the value of next_delay for example by doubling it. However the value of next_delay cannot exceed the maximum delay value A. In particular the computing node computes next_delay=MIN (A, next_delay*2). The algorithm then loops back to block 102.
As a result the computing node will react very quickly to a newly received LSP if it is the first LSP or if it is received after a quiet period. However the algorithm increases the delay between consecutive computations by incrementing the value of C if such computations have to be done in a short period of time. A problem with this approach, however, is that in some instances SPF computations can be delayed to a significant extent. This can give rise to problems when a network change occurs requiring rapid response. In addition in some instances as a result of the delay looping can take place. This can arise because of discrepancies between SPTs on different nodes where each node implements lengthy delays or delays of different periods.